#include <iostream>
#include <cstring>

using namespace std;

void computeNext(const char* b, int* next, int len) {
    int j = 0;  // next[j] 表示长度为 j 的子串的最长相等前后缀长度
    next[0] = 0;  // 初始值
    int i = 1;  // 当前子串的长度

    while (i < len) {
        if (b[i] == b[j]) {
            next[i] = j + 1;  // 如果当前字符匹配，最长相等前后缀长度加1
            i++;
            j++;
        } else {
            if (j != 0) {
                j = next[j - 1];  // 回退到前一个最长相等前后缀的末尾
            } else {
                next[i] = 0;  // 如果 j=0，说明没有匹配的前后缀
                i++;
            }
        }
    }
}

int KMP(const char* a, const char* b) {
    int lenA = strlen(a);
    int lenB = strlen(b);

    int* next = new int[lenB];  // 动态分配 next 数组
    computeNext(b, next, lenB);

    int i = 0;  // a 的下标
    int j = 0;  // b 的下标

    while (i < lenA) {
        if (a[i] == b[j]) {
            i++;
            j++;
        }

        if (j == lenB) {
            delete[] next;  // 释放 next 数组
            return i - j;  // 匹配成功，返回起始位置
        } else if (i < lenA && a[i] != b[j]) {
            if (j != 0) {
                j = next[j - 1];  // 匹配失败，根据 next 数组回退
            } else {
                i++;
            }
        }
    }

    delete[] next;  // 释放 next 数组
    return -1;  // 匹配失败
}

int main() {
    char S[] = "1234567";
    char T0[] = "56";
    char T1[] = "54";

    cout << KMP(S, T0) << endl;  // 输出匹配位置
    cout << KMP(S, T1) << endl;  // 输出匹配位置

    return 0;
}